class Solution188 {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length ; 
        // 第 i 天 结束, 完成j 次交易, 处于买入状态 , 最大利润
        int[][] f = new int[n][k+1] ; 
        // 第 i 天 结束 , 完成 j 次交易 , 处于卖出状态 , 最大利润
        int[][] g = new int[n][k+1] ;
        // 初始化 方便后面求 max最大值
        for(int i=0 ; i <= k ; i ++){
           f[0][i] = -0x3f3f3f3f ;    // 防止int越界,用 最大值/2
        }
        f[0][0] = -prices[0] ;
        
        for(int i=1 ; i < n ; i ++){
            for(int j=0 ; j <= k ; j ++){
               f[i][j] = Math.max(f[i-1][j] , g[i-1][j] - prices[i]) ;
               g[i][j] = g[i-1][j] ; 
               if(j >= 1) g[i][j] = Math.max(g[i][j] , f[i-1][j-1] + prices[i]) ; 
            }
        }
        // 返回最后一行 处于卖出状态 的最大值 
       int max = 0 ; 
       for(int i=0 ; i <= k ; i ++){
         max = Math.max(max , g[n-1][i]) ; 
       }

     return max ; 
    }
}